Let u,v ϵ ℝ^Ω_+ be positive unit vectors and S ϵ ℝ^{Ω×Ω}_+ be a symmetric substochastic matrix. For an integer t ≥ 0, let m_t = ⟨v,S^tu⟩, which we view as the heat measured by v after an initial heat configuration u is let to diffuse for t time steps according to S. Since S is entropy improving, one may intuit that m_t should not change too rapidly over time. We give the following formalizations of this intuition.

We prove that m_{t+2} ≥ m_t^{1+2/t}, an inequality studied earlier by Blakley and Dixon (also Erdős and Simonovits) for u=v and shown true under the restriction m_t ≥ e^{-4t}. Moreover we prove that for any ε>0, a stronger inequality m_{t+2} ≥ t^{1-ε} ⋅ m_t^{1+2/t} holds unless m_{t+2}m_{t-2} ≥ δ m_t^2 for some δ that depends on ε only. Phrased differently, ∀ ε> 0, ∃ δ > 0 such that ∀ S,u,v:

m_{t+2} / {m_{t}^{1+2/t} ≥ min { t^{1-ε}, δm_t^{1-2/t} / m_{t-2} }, ∀ t ≥ 2,

which can be viewed as a truncated log-convexity statement.

Using this inequality, we answer two related open questions in complexity theory: Any property tester for k-linearity requires Ω(k log k) queries and the randomized communication complexity of the k-Hamming distance problem is Ω(k log k). Further we show that any randomized parity decision tree computing k-Hamming weight has size exp(Ω(k log k).